1. Technical Field of the Invention
The present invention relates to a method for generating volume data that enables CAD and simulation to be unified by storing the volume data that includes shapes and physical properties with a small storage capacity, and more particularly to a method and program for converting boundary data of an object, which has been input to a computer, into cell inner shape data in a cell complex, which is composed of rectangular parallelepiped cells each having boundary surfaces crossing each other without gaps between the rectangular parallelepiped cells.
2. Description of the Related Art
The present inventor et al. devised and applied for a patent on a “method for storing substantial data that includes shapes and physical properties” (Patent Document 1).
According to this invention, as schematically shown in FIG. 8, external data composed of boundary data of an object is divided into rectangular parallelepiped cells whose boundary surfaces cross each other by octree division, and the cells are classified into nonboundary cells 13a located inside or outside the object and boundary cells 13b each containing a boundary surface. In this figure, a reference numeral 15 denotes a cutting point.
According to this invention, substantial data that includes shapes and physical properties can be stored in a unified manner by storing various physical property values for each cell. Thus, a shape, structure, physical property information, and hysteresis of an object can be managed in a unified manner to enable management of data on a series of processes from designing to fabricating, assembling, testing, evaluation and the like based on the same data, whereby it is possible to unify CAD and simulation.
Hereinafter, in the present application, the rectangular parallelepiped cell whose boundary surfaces cross each other is referred to as “volume cell,” data for which various physical property values are stored for each cell is referred to as “volume data,” and simulation means with the volume data is referred to as “volume CAD” or “VCAD.”
Moreover, the present inventor et al. suggest Patent Documents 2 to 4 as means for generating volume data from boundary representation data.
Moreover, Patent Document 5 and Non-patent Documents 1 to 6 have been disclosed as conventional technologies related to the present invention.
The method in the Patent Document 2 includes an octree division step, a cell classification step, a cutting point deciding step, and a boundary surface deciding step. Particularly, cells are classified as a different type of boundary cells according to the number of cutting points, the combination of edges to be cut is previously set for each boundary cell type, and the boundary cell type and the combination are acquired by pattern matching based on the acquired number of cutting points and the cut edges.
The method in the Patent Document 3 includes a division step, a cutting point deciding step, a boundary deciding step, a cell classification step, and a boundary cell data classification step. Particularly, in the three-dimensional cell, in the cutting point deciding step, intersection point patterns of boundary data and cell edges that have totally 212=4096 arrangement cases are decided as the cell edge cutting points, and the arrangement cases that become equivalence classes by rotational operation and mirroring operation are decided as identical patterns so that the 212=4096 arrangement cases are further classified into 144 patterns.
The method in the Patent Document 4 includes inputting boundary representation data of an object into a computer using external data input means, converting the boundary representation data to triangular patches with topology using data conversion means, dividing a space into rectangular parallelepiped cells whose boundary surfaces cross each other and associating cells with triangles included therein using association means, dividing the triangular patches with topology that appeared in the space by cell surfaces using division and arrangement means so that all triangles are arranged inside the cells or on the boundaries, integrating edges not to be changed in topology using edge integration means, assigning the respective triangles and their vertices to the cells with reference to index data of the vertices using cell assignment means, and setting attribute values of the cells using labeling means.
[Patent Document 1]
Japanese Patent No. 3468464, “Method for Storing Substantial Data that includes Shapes and Physical Properties”
[Patent Document 2]
International Publication No. WO 03/048980, “Method and Program for Converting Three-Dimensional Shape Data into Cell Internal Data”
[Patent Document 3]
International Publication No. WO 03/073335, “Method and Program for Converting Boundary Data into Cell Inner Shape”
[Patent Document 4]
Japanese Laid-Open Patent Publication No. 2005-38219, “Method and Program for Generating Volume Data from Boundary Representation Data”
[Patent Document 5]
Japanese Laid-Open Patent Publication No. 2003-44528, “Method for Generating Surface Grid of Object”
[Non-Patent Document 1]
H. Hoppe, “Progressive meshes,” Proc. SIGGRAPH '96, pp. 99-108, August 1996
[Non-Patent Document 2]
W. J. Shroeder, “A Topology Modifying Progressive Decimation Algorithm,” Proc. Visualization '97, pp. 205-212, October 1997
[Non-Patent Document 3]
W. J. Shroeder, J. A. Zarge and W. E. Lorensen, “Decimation of Triangle Meshes,” Proc. SIGGRAPH '92, pp. 65-70, July 1992
[Non-Patent Document 4]
K. J. Renze and J. H. Oliver, “Generalized Surface and Volume Decimation for Unstructured Tessellated Domains,” Proc. VRAIS '96, pp. 111-121, March 1996
[Non-Patent Document 5]
K. Kase, et al., “volume CAD,” Volume Graphics (2003)
[Non-Patent Document 6]
Piegl L., Richard M., “Tessellating Trimmed NURBS Surfaces,” Computer-Aided Design, 1995; 27(1): 16-26
The method for generating a shape representation with cells and rectangular patches adapted to the cells and data therefor, which have been suggested in the Patent Documents 2 and 3, is performed in the following steps:
(Step 1) calculating intersection points between a cell space defined by a user and a rectangular patch as an input shape (calculating cell cutting points);
(Step 2) generating a closed loop formed by connecting the cell cutting points on a cell surface for each cell (on this occasion, the cell cutting points are determined in the order in which the cutting points are uniquely determined based on the number of cell cutting points in the cell or the relation with the neighboring cells); and(Step 3) carrying out triangulation based on a difference from the input shape within the closed loop generated in each cell.
This method, however, has the following problems.
(1) There is a case where the processing of (Step 2) is not completed for a shape having the same level of complexity as the cell size of the volume cell.
(2) There is a case where the processing of (Step 2) is unsuccessful because a non-manifold shape appears in the process of gradually changing from a smaller shape than the cell size to a large shape.
(3) In view of considering that the cells are hierarchized, it is extremely difficult to retrieve the adjacency relation in the processing of (Step 2).
To resolve these problems, the Patent Document 4 describes means for directly using topology information of a rectangular patch of an input shape and simplifying the shape, if necessary, and the means includes:
(Step 1) converting an original surface patch (boundary representation data) to a triangular patch with topology;
(Step 2) dividing the triangular patch with topology into cell surfaces (rectangular parallelepiped cells whose boundary surfaces cross each other);
(Step 3) integrating vertices not on the cell edges among the vertices of the triangular patch with topology into other vertices; and
(Step 4) carrying out optimization by approximating a portion contrary to the condition of Step 3 or to the basic condition of the volume data, “only one cutting point per edge of the rectangular parallelepiped cell.”
The above means enables robust calculation according to the geometric shape to be input.
On the other hand, however, this means has a problem of high load on calculation for representing a complicated shape, which leads to a limitation on a single personal computer (PC) to deal with massive data. Therefore, there has been a demand for processing means whose load on calculation is relatively low.
There has already been suggested a method for dividing a rectangular patch into portions each having almost the same size as the cell size so as to be managed by cells [Patent Document 5]. In this method, however, the rectangular patch does not adapt to the cell and one-to-one management cannot be provided for the cell and the rectangular patch. Therefore, it is not applicable to a unified data management from upstream to downstream processes in manufacturing, which is the purpose of VCAD.
Furthermore, regarding the processing using a triangular patch alone, a method for carrying out detailed or simplified shape representation by subdividing or integrating triangular patches has already been suggested by Hoppe et al. [Non-patent Document 1], and various derived systems exist according to a subdividing parameter or a subdividing method or according to the decision criterion for integration. These systems, however, adopt a conversion method with the two-manifold condition and topology condition inherited directly from those of the original shape. Therefore, they are unsuitable for operations of intentionally simplifying a minute shape or performing non-manifold representation of a surface having branches or edges [Non-patent Documents 2, 3, and 4].